/*
 * @lc app=leetcode.cn id=33 lang=cpp
 *
 * [33] 搜索旋转排序数组
 */

// @lc code=start
class Solution
{
 public:
  int search(vector<int>& nums, int target)
  {
    if (nums.empty()) return -1;
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = (l + r) >> 1;
      if (nums[mid] <= nums.back())
        r = mid;
      else
        l = mid + 1;
    }
    // 找到最小值了就在l, 现在看target是在哪一个单调区间
    if (target <= nums.back())
      r = nums.size() - 1;  // 在左边单调区间
    else
      l = 0, r--;

    // 在一次二分
    while (l < r)
    {
      int mid = (l + r) >> 1;
      if (nums[mid] <= target)
        l = mid;
      else
        r = mid - 1;
    }

    if (nums[l] == target) return 1;
    return -1;
  }
};
// @lc code=end
